<?xml version="1.0" encoding="UTF-8"?>
<Export generator="Cache" version="25" zv="Cache for UNIX (Apple Mac OS X for x86-64) 2014.1 (Build 601U)" ts="2014-03-05 15:01:46">
<Class name="com.example.BinarySearch">
<Description>
$Author: andrey.shcheglov@intersystems.com $
$Revision: 7 $
$Date: 2014-03-05 11:06:01 +0000 (Wed, 05 Mar 2014) $</Description>
<TimeChanged>63251,53858.563212</TimeChanged>
<TimeCreated>63158,69619.071208</TimeCreated>

<Method name="BinarySearchList">
<ClassMethod>1</ClassMethod>
<FormalSpec>data:%ListOfDataTypes,key:%Integer</FormalSpec>
<ReturnType>%Integer</ReturnType>
<Implementation><![CDATA[
	if (data = "") {
		throw ##class(%Exception.General).%New(, , , "list is null")
	}
	
	if (data.Size = 0) {
		return -1
	}

	#dim low as %Integer = 0
	#dim high as %Integer = data.Size - 1
	while (low < high) {
		#dim middle as %Integer = low + ((high - low) \ 2)
		if (data.GetAt(middle + 1) = key) {
			return middle
		}

		if (data.GetAt(middle + 1) < key) {
			set low = middle + 1
		} else {
			set high = middle - 1
		}
	}

	return $select(data.GetAt(low + 1) = key: low, 1: -1)
]]></Implementation>
</Method>

<Method name="BinarySearchArray">
<Description>
The first index in the associative array is assumed to be 0</Description>
<ClassMethod>1</ClassMethod>
<FormalSpec>data:%ArrayOfDataTypes,key:%Integer</FormalSpec>
<ReturnType>%Integer</ReturnType>
<Implementation><![CDATA[
	if (data = "") {
		throw ##class(%Exception.General).%New(, , , "array is null")
	}

	if (data.Count() = 0) {
		return -1
	}

	#dim low as %Integer = 0
	#dim high as %Integer = data.Count() - 1
	while (low < high) {
		#dim middle as %Integer = low + ((high - low) \ 2)
		if (data.GetAt(middle) = key) {
			return middle
		}

		if (data.GetAt(middle) < key) {
			set low = middle + 1
		} else {
			set high = middle - 1
		}
	}
	
	return $select(data.GetAt(low) = key: low, 1: -1)
]]></Implementation>
</Method>

<Method name="TestList">
<ClassMethod>1</ClassMethod>
<Implementation><![CDATA[
	#dim b as list of %Integer = ##class(%ListOfDataTypes).%New()
	set b.ElementType = "%Integer"
	do b.Insert(1)
	do b.Insert(2)
	do b.Insert(3)
	do b.Insert(4)
	do b.Insert(555)
	do b.Insert(800)
	do b.Insert(999)
	do b.Insert(1024)
	do b.Insert(2048)
	do b.Insert(4096)

	write ..BinarySearchList(b, 4096), !
	write ..BinarySearchList(b, 2048), !
	write ..BinarySearchList(b, 1024), !
	write ..BinarySearchList(b, 999), !
	write ..BinarySearchList(b, 800), !
	write ..BinarySearchList(b, 555), !
	write ..BinarySearchList(b, 4), !
	write ..BinarySearchList(b, 3), !
	write ..BinarySearchList(b, 2), !
	write ..BinarySearchList(b, 1), !
]]></Implementation>
</Method>

<Method name="TestArray">
<ClassMethod>1</ClassMethod>
<Implementation><![CDATA[
	#dim c as array of %Integer = ##class(%ArrayOfDataTypes).%New()
	set c.ElementType = "%Integer"
	do c.SetAt(4096,	9)
	do c.SetAt(2048,	8)
	do c.SetAt(1,	0)
	do c.SetAt(2,	1)
	do c.SetAt(3,	2)
	do c.SetAt(4,	3)
	do c.SetAt(555,	4)
	do c.SetAt(800,	5)
	do c.SetAt(999,	6)
	do c.SetAt(1024,	7)
	
	write ..BinarySearchArray(c, 4096), !
	write ..BinarySearchArray(c, 2048), !
	write ..BinarySearchArray(c, 1024), !
	write ..BinarySearchArray(c, 999), !
	write ..BinarySearchArray(c, 800), !
	write ..BinarySearchArray(c, 555), !
	write ..BinarySearchArray(c, 4), !
	write ..BinarySearchArray(c, 3), !
	write ..BinarySearchArray(c, 2), !
	write ..BinarySearchArray(c, 1), !
]]></Implementation>
</Method>

<Method name="Main">
<ClassMethod>1</ClassMethod>
<Implementation><![CDATA[
	do ..TestList()
	do ..TestArray()
]]></Implementation>
</Method>
</Class>
</Export>
